package hot_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class 找到字符串中所有字母异位词 {
    public static void main(String[] args) {
        List<Integer> anagrams = findAnagrams("cbaebabacd", "abc");
        for (Integer anagram : anagrams) {
            System.out.println(anagram);
        }
    }

    public static List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length())
            return Collections.emptyList();
        List<Integer> ans = new ArrayList<>();
        int[] chp = new int[26];
        char[] pp = p.toCharArray();
        int[] chs = new int[26];
        char[] ss = s.toCharArray();

        for (char c : pp) {
            chp[c - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            int j = i - p.length() + 1;
            chs[ss[i] - 'a']++;
            if (j < 0) {
                continue;
            }
            if (Arrays.equals(chp, chs)) {
                ans.add(j + 1);
            }
            chs[ss[j] - 'a']--;
        }
        return ans;
    }
}
